﻿//1577. 数的平方等于两数乘积的方法数
//给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
//类型 1：三元组(i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
//类型 2：三元组(i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length


class Solution {
public:
    int f(vector<int>& nums1, vector<int>& nums2)
    {
        int ans = 0;
        sort(nums2.begin(), nums2.end());
        for (int i = 0; i < nums1.size(); i++)
        {
            long long x = 1L * nums1[i] * nums1[i];
            int left = 0, right = nums2.size() - 1;
            while (left < right)
            {
                long long s = 1L * nums2[left] * nums2[right];
                if (s > x)     right--;
                else if (s < x)    left++;
                else
                {
                    if (nums2[left] == nums2[right])
                    {
                        ans += (right - left + 1) * (right - left) / 2;
                        break;
                    }
                    else
                    {
                        int t1 = 0, t2 = 0;
                        int l = nums2[left], r = nums2[right];
                        while (l == nums2[left])
                            t1++, left++;
                        while (r == nums2[right])
                            t2++, right--;
                        ans += t1 * t2;
                    }
                }
            }
        }
        return ans;
    }

    int numTriplets(vector<int>& nums1, vector<int>& nums2)
    {
        return f(nums1, nums2) + f(nums2, nums1);
    }
};